//
// Created by 麻再挺 on 2021/12/15.
//

#include "huffman_tree.h"

/**
 * 选取哈夫曼树最小的两个结点索引, 保证s1 最小
 * @param t 哈夫曼树
 * @param end 存放结点的最终位置
 * @param s1 存储结点权重值的数组中最小的数1
 * @param s2 存储结点权重值的数组中最小的数1
 */
void Select_Huffman_Tree(HuffmanTree t, int i, int *pInt, int *pInt1);

/**
 * 创建哈夫曼树
 * @param t 树
 * @param w 节点数组
 * @param n 长度
 */
void CreateHuffmanTree(HuffmanTree *t, int *w, int n) {
    // 如果只有一个节点则直接返回
    if (n <= 1) return;
    // 哈夫曼树的总结点数
    int m = 2 * n - 1;
    // 申请内存
    *t = malloc((m + 1) * sizeof(HTNode));
    HuffmanTree p = *t;
    // 初始化哈夫曼树中的所有结点
    for (int i = 1; i <= n; ++i) {
        (p + i)->weight = *(w + i - 1);
        (p + i)->parent = 0;
        (p + i)->left = 0;
        (p + i)->right = 0;
    }
    // 初始化哈夫曼树中除叶子结点的所有结点
    for (int i = n + 1; i <= m; ++i) {
        (p + i)->weight = 0;
        (p + i)->parent = 0;
        (p + i)->left = 0;
        (p + i)->right = 0;
    }
    // 构建哈夫曼树
    for (int i = n + 1; i <= m; ++i) {
        // 存储结点权重值的数组中最小的两个数索引
        int s1, s2;
        // 挑选出最小的两个数索引
        Select_Huffman_Tree(*t, i - 1, &s1, &s2);
        // 赋值
        (*t)[s1].parent = (*t)[s2].parent = i;
        (*t)[i].left = s1;
        (*t)[i].right = s2;
        (*t)[i].weight = (*t)[s1].weight + (*t)[s2].weight;
    }
}


/**
 * 打印
 * @param t 哈夫曼树
 * @param w 结点
 * @param n 数量
 */
void PrintHuffmanTree(HuffmanTree t, int n) {
    for (int i = 1; i <= 2 * n - 1; ++i) {
        printf("weight: %d, parent: %d, left: %d, right: %d\n", t[i].weight, t[i].parent, t[i].left, t[i].right);
    }
}

/**
 * 选取哈夫曼树最小的两个结点索引, 保证s1 最小
 * @param t 哈夫曼树
 * @param end 存放结点的最终位置
 * @param s1 存储结点权重值的数组中最小的数1
 * @param s2 存储结点权重值的数组中最小的数1
 */
void Select_Huffman_Tree(HuffmanTree t, int end, int *s1, int *s2) {
    int min1, min2;
    // 遍历数组, 初始下标为 1
    int i = 1;
    // 如果 parent 为0, 则说明还未找到, 遍历
    while (t[i].parent != 0 && i < end) i++;
    // 第一个值
    min1 = t[i].weight;
    *s1 = i;
    // 移动索引
    i++;
    // 查找第二个
    while (t[i].parent != 0 && i <= end) {
        i++;
    }
    // 对找到的两个结点比较大小，min2为大的，min1为小的
    if (t[i].weight < min1) {
        // 交换最小索引和值
        min2 = min1;
        *s2 = *s1;
        min1 = t[i].weight;
        *s1 = i;
    } else {
        min2 = t[i].weight;
        *s2 = i;
    }
    // 两个结点及后续的所有未构建的结点作比较
    for (int j = i + 1; j <= end; ++j) {
        // 如果有结点则跳过
        if (t[j].parent != 0) continue;
        // 如果比最小的还小, 则交换值min2 = min1, min1赋值新的结点的下标
        if (t[j].weight < min1) {
            min2 = min1;
            *s2 = *s1;
            min1 = t[j].weight;
            *s1 = j;
        }
            // 如果介于两者之间，min2赋值为新的结点的位置下标
        else if (t[j].weight >= min1 && t[j].weight < min2) {
            min2 = t[j].weight;
            *s2 = j;
        }
    }
}

/**
 * 哈夫曼编码
 * @param t 树
 * @param code 编码
 * @param n 长度
 */
void HuffmanCoding(HuffmanTree t, HuffmanCode *code, int n) {
    // 申请内存
    *code = malloc(sizeof(char *) * (n + 1));
    // 存放哈夫曼编码的字符串数组
    char *codes = malloc(n * sizeof(char));
    // 字符串结束标识
    codes[n - 1] = '\0';

    // 遍历
    for (int i = 1; i <= n; ++i) {
        // 从叶子结点出发, 得到的哈夫曼编码是逆序的
        int start = n - 1;
        // 当前结点在数组中的位置
        int c = i;
        // 当前结点的父节点在数组中的位置
        int j = t[i].parent;
        // 一直寻找到根节点
        while (j != 0) {
            // / 如果该结点是父结点的左孩子则对应路径编码为0，否则为右孩子编码为1
            if (t[j].left == c) {
                codes[--start] = '0';
            } else {
                codes[--start] = '1';
            }
            // 以父结点为孩子结点，继续朝树根方向遍历
            c = j;
            // 查找父节点
            j = t[j].parent;
        }
        // 跳出循环后, codes树中从下标 start 开始, 存放的就是该结点的哈夫曼编码
        (*code)[i] = malloc((n - start) * sizeof(char));
        strcpy((*code)[i], &codes[start]);
    }
    // 使用malloc申请的内存需要手动释放
    free(codes);
}

/**
 * 输出哈夫曼编码
 * @param code 编码
 * @param w 节点
 * @param n 长度
 */
void PrintHuffmanCode(HuffmanCode code, int *w, int n) {
    printf("Huffman code : \n");
    for (int i = 1; i <= n; i++)
        printf("%d code = %s\n", w[i - 1], code[i]);
}